package vip.zhenzicheng.algorithm.leetcode.binary_search;

/**
 * <a href="https://leetcode.cn/problems/median-of-two-sorted-arrays/">寻找两个正序数组的中位数</a>
 * 要求算法的时间复杂度为O(log (m+n))
 *
 * @author zhenzicheng
 * @date 2022-06-21 13:07
 */
public class MedianOfTwoSortedArrays_4 {

  public static void main(String[] args) {
    MedianOfTwoSortedArrays_4 test = new MedianOfTwoSortedArrays_4();
    int[] nums1 = new int[]{1, 3};
    int[] nums2 = new int[]{2};
    double result = test.findMedianSortedArrays(nums1, nums2);
    System.out.println(result);
  }

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    // 不论合并数组的长度是奇数还是偶数，都可以用这样的方式求解中位数
    int left = (nums1.length + nums2.length + 1) / 2;
    int right = (nums1.length + nums2.length + 2) / 2;
    // 合并数组长度是奇数则相加再除2等于本身，如果是偶数正好是中间两个数的平均值即中位数
    return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
  }

  public int findKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
    // 如果超出边界，返回另一个数组的中位数
    if (start1 >= nums1.length) return nums2[start2 + k - 1];
    if (start2 >= nums2.length) return nums1[start1 + k - 1];
    if (k == 1) { // 只有1个数返回小数
      return Math.min(nums1[start1], nums2[start2]);
    }

    int midVal1 = (start1 + k / 2 - 1) < nums1.length ? nums1[start1 + k / 2 - 1] : Integer.MAX_VALUE;
    int midVal2 = (start2 + k / 2 - 1) < nums2.length ? nums2[start2 + k / 2 - 1] : Integer.MAX_VALUE;

    if (midVal1 < midVal2) { // 清除该中位数左边的所有元素并递归
      return findKth(nums1, start1 + k / 2, nums2, start2, k - k / 2); // 中位数位置也需要减去清除数组的长度
    } else {
      return findKth(nums1, start1, nums2, start2 + k / 2, k - k / 2);
    }
  }
}
